Merge two binary trees [Recursion]

Time: O(N); Space: O(H); easy

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree.

The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

  Tree 1                     Tree 2
    1                         2
   / \                       / \
  3   2                     1   3
 /                           \   \
5                             4   7

Input: t1 = {TreeNode} [1,3,2,5], t2 = {TreeNode} [2,1,3,#,4,#,7]

Output: {TreeNode} [3,4,5,5,4,#,7]

    3
   / \
  4   5
 / \   \
5   4   7

[4]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

Auxiliary Tools

[5]:

from graphviz import Graph

class TreeTasks(object):
    def visualize_tree(self, tree):
        def add_nodes_edges(tree, dot=None):
            # Create Graph (not Digraph) object
            if dot is None:
                dot = Graph()
                dot.node(name=str(tree), label=str(tree.val))
            # Add nodes
            if tree.left:
                dot.node(name=str(tree.left), label="."+str(tree.left.val))
                dot.edge(str(tree), str(tree.left))
                dot = add_nodes_edges(tree.left, dot=dot)
            if tree.right:
                dot.node(name=str(tree.right), label=str(tree.right.val)+".")
                dot.edge(str(tree), str(tree.right))
                dot = add_nodes_edges(tree.right, dot=dot)
            return dot
        # Add nodes recursively and create a list of edges
        dot = add_nodes_edges(tree)
        # Visualize the graph
        display(dot)
        return dot

1. Using Recursion

  1. We can traverse both the given trees in a preorder fashion.

  2. At every step, we check if the current node exists(isn’t null) for both the trees.

  3. If so, we add the values in the current nodes of both the trees and update the value in the current node of the first tree to reflect this sum obtained.

  4. At every step, we also call the original function mergeTrees() with the left children and then with the right children of the current nodes of the two trees.

  5. If at any step, one of these children happens to be null, we return the child of the other tree(representing the corresponding child subtree) to be added as a child subtree to the calling parent node in the first tree.

  6. At the end, the first tree will represent the required resultant merged binary tree.

[6]:

class Solution1(object):
    def mergeTrees(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode
        """
        if t1 is None:
            return t2
        if t2 is None:
            return t1

        t1.val += t2.val

        t1.left = self.mergeTrees(t1.left, t2.left)

        t1.right = self.mergeTrees(t1.right, t2.right)

        return t1

[7]:

s = Solution1()

t1 = TreeNode(1)
t1.left = TreeNode(3)
t1.right = TreeNode(2)
t1.left.left = TreeNode(5)

t2 = TreeNode(2)
t2.left = TreeNode(1)
t2.right = TreeNode(3)
t2.left.right = TreeNode(4)
t2.right.right = TreeNode(7)
tree = s.mergeTrees(t1, t2)

t = TreeTasks()
dot = t.visualize_tree(tree)

# assert res.val == 3
# assert res.left.val == 4
# assert res.right.val == 5
# assert res.left.left.val == 5
# assert res.left.right.val == 4
# assert res.right.right.val == 7
../../_images/topics_tree_0617_merge_two_binary_trees_[O(N),O(H),easy]_6_0.svg